class Solution:
    def maxValue(self, grid) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = [0 for _ in range( n)]
        for i in range(0, m):
            for j in range(0, n):
                left,up = 0,0
                if i > 0:
                    up = ans[j]
                if j > 0:
                    left = ans[j-1]

                ans[j] = max(up, left) + grid[i][j]
        return ans[j]

ans= Solution()
xx = ans.maxValue(grid=[[1,10,3,8],[12,2,9,6],[5,7,4,11],[3,7,16,5]])